#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-31 10:12 上午
# @Author  : yangdy
# @File    : 2020-07-31.面试题08.03.魔术索引
# @Software: PyCharmCE
from my_methods import *


class Solution:
    def findMagicIndex(self, nums: List[int]) -> int:
        ln = len(nums)
        ans = 0
        # 1. 暴力枚举 o(n)
        # while ans < ln:
        #     if nums[ans] == ans:
        #         break
        #     ans += 1
        # else:
        #     ans = -1
        # 2. 坐标滑动
        while ans < ln and ans != nums[ans]:
            if ans < nums[ans]:
                ans = nums[ans]
            else:
                ans += 1
        ans = ans if ans < ln else -1

        # 3. 二分枚举 o(logn) ?
        # l, r = 0, ln-1
        # while l < r:
        #     h = (l + r) // 2
        #     x = nums[h]
        #     print(l, f'{h}:{x}', r)
        #     if x > h:
        #         r = h - 1
        #     elif x < h:
        #         l = h + 1
        #     else:
        #         r = h
        #
        # def work(a, ll, rr):
        #
        #     return
        #
        # ans = l
        return ans


questions = [
    ([0, 2, 3, 4, 5],),
    ([1, 1, 1],),
]

work(questions, lambda q: Solution().findMagicIndex(q[0]))
